Many of the tasks that are addressed by decision-making systems and artificial intelligence can be framed as constraint satisfaction problems (CSPs). In this framework, the task is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of predicates, or constraints, that the variables are expected to satisfy. (The constraints may include “hard constraints,” which must be satisfied by solutions to the CSP, and “soft constraints,” which may not be satisfied by all solutions.) The set of variables and constraints is referred to as a constraint network. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to the problem is an assignment of a value to each variable from its domain that satisfies all of the hard constraints.
Constraint satisfaction methods have been found useful in a variety of applications, including:                Artificial intelligence        Robotic control        Temporal reasoning        Natural language parsing        Spatial reasoning        Test generation for software and hardware systems        Machine vision        Medical diagnosis        Resource allocation        Crew scheduling        Time tabling        Frequency allocation        Graph coloring.        
For example, Bin et al. describe a constraint satisfaction method for use in automated testing of hardware circuits, in a paper entitled “Using a Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation,” IBM Systems Journal 41:3 (2002), pages 386–402, which is incorporated herein by reference. The authors use an analytical constraint satisfaction algorithm to generate addresses and memory access instructions that provide effective verification of the design of a computer processor. This algorithm, which is based on maintaining arc consistency in the constraint network, is described further by Emek et al. in U.S. patent application Ser. No. 09/788,152, published as U.S. Patent Application Publication 2002/0169587 A1, which is assigned to the assignee of the present patent application, and whose disclosure is incorporated herein by reference.
Stochastic techniques for CSP solving are also known in the art. For example, U.S. Pat. No. 5,636,328, whose disclosure is incorporated herein by reference, describes methods and apparatus for finding values that satisfy a set of constraints, applied particularly to control of a robotic arm. The technique described in this patent is used in local search procedures for finding such constraint-satisfying values, with the aim of overcoming the tendency of such local search procedures to “get stuck” at certain points in the search.
Another stochastic CSP solving technique, known as GSAT, is described by Selman et al., in “A New Method for Solving Hard Satisfiability Problems,” Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92, San Jose, Calif., 1992), pages 440–446, whose disclosure is incorporated herein by reference. GSAT performs a greedy local search for a satisfying assignment of a set of propositional clauses. It then changes the assignment of the variable that leads to the largest increase in the total number of satisfied clauses, repeating this procedure until a satisfying assignment is found (or until time runs out). GSAT mimics standard local search procedures used for finding approximate solutions to optimization problems, in that it explores only potential solutions that are “close” to the one currently being considered, although it may also include “sideways” moves.